package com.bo.day20231221;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * leetcode: https://leetcode.cn/problems/intersection-of-two-linked-lists/
 * 情况如下：
 * headA 无环,headB 无环  可能会相交
 * headA 有环,headB 无环   不会相交
 * headA 无环,headB 有环   不会相交
 * headA 有环,headB 有环   可能会相交
 *
 * @Author: gpb
 * @Date: 2024/1/3 11:21
 * @Description:
 */
public class GetIntersectionNode {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode (int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode (ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 获取环节点
        ListNode loopA = getLoopNode(headA);
        ListNode loopB = getLoopNode(headB);
        // 是无环的情况下
        if (loopA == null && loopB == null) {
            return noLoop(headA, headB);
        }
        // 两个都有环的情况下
        if (loopA != null && loopB != null) {
            return bothLoop(headA, loopA, headB, loopB);
        }
        return null;
    }

    public static ListNode bothLoop (ListNode headA, ListNode loopA, ListNode headB, ListNode loopB) {
        ListNode cur1 = null;
        ListNode cur2 = null;
        // 两个环相等的情况下
        if (loopA == loopB) {
            cur1 = headA;
            cur2 = headB;
            int n = 0;
            while (cur1 != loopA) {
                cur1 = cur1.next;
                n++;
            }
            while (cur2 != loopB) {
                cur2 = cur2.next;
                n--;
            }
            cur1 = n > 0 ? headA : headB;
            cur2 = cur1 == headA ? headB : headA;
            n = Math.abs(n);
            // 走步差
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
        // 如果环不相等,如需要走一个链表就行,走到转到环为止
        cur1 = loopA.next;
        while (cur1 != loopA) {
            if (cur1 == loopB) {
                return loopA;
            }
            cur1 = cur1.next;
        }
        return null;
    }

    /**
     * 无环情况下
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode noLoop (ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n = 0;
        while (cur1.next != null) {
            cur1 = cur1.next;
            n++;
        }
        // 找到步差
        while (cur2.next != null) {
            cur2 = cur2.next;
            n--;
        }
        // 如果最后一个元素不相等,说明headA,headB不相交
        if (cur1 != cur2) {
            return null;
        }
        // 找到那个是最长的链表
        cur1 = n > 0 ? headA : headB; // 如果n>大于0,说明headA是那个长链表
        cur2 = cur1 == headA ? headB : headA; // 那个短,短的链表
        // 长链表,先步差走完
        n = Math.abs(n);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        // 现在cur1和cur2一样长了,一起走,找到那个第一个相交的节点
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    /**
     * 找到链表第一个入环节点,如果无环,返回null
     *
     * @param head
     * @return
     */
    public static ListNode getLoopNode (ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        // 慢指针,一次走一部
        ListNode slow = head.next;
        // 快指针,一次走两部
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        // 快指针回头头节点,一次走一步
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
